P2486 [SDOI2011]染色

发表于

闲扯

把代码删了重写真好用！！

挺好的一道树剖套线段树的裸题

题面

P2486 [SDOI2011]染色

Solution

套路性的树剖 $+$ 线段树来维护一下树上路径之间的问题。

先考虑对于一个数组怎么维护。

可以发现，我们需要额外记录两个值 $l_ty,r_ty$ 来表示该区间最左边和最右边的颜色。

合并的时候，如果左儿子的 $r_ty$ 等于有儿子的 $l_ty$ ，我们需要将答案减一。

那么对于树上的情况，这个依然适用。

但对于树剖查询时，每次向上跳之前，我们要看看 $top[u],f[top[u]]$ 的颜色是否相同，如果相同，答案减一。

还有就是线段树查询的时候，判断条件要改一下。

如果整个区间全部在左儿子，直接查询左儿子；如果全部在右儿子，直接查询右儿子。

否则，我们查询完左右儿子之后，我们还要看看中间的颜色是否相等。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il print(T x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 1e5+5;
int n,m,val[MAXN],u,v,head[MAXN],num_edge,k;
char opt[2];
struct Edge{
	int next,to;
	Edge(){}
	Edge(int next,int to):next(next),to(to){}
}edge[MAXN<<1];
il add_edge(int u,int v){
	edge[++num_edge]=Edge(head[u],v),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u),head[v]=num_edge;
}
int d[MAXN],son[MAXN],f[MAXN],sz[MAXN],top[MAXN],id[MAXN],rk[MAXN],cnt;
il DFS1(int u,int fa){
	d[u]=d[fa]+1,f[u]=fa,sz[u]=1;
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		DFS1(edge[i].to,u),sz[u]+=sz[edge[i].to];
		if(sz[edge[i].to]>sz[son[u]]) son[u]=edge[i].to;
	}
}
il DFS2(int u,int t){
	top[u]=t,id[u]=++cnt,rk[cnt]=u;
	if(!son[u]) return ;
	DFS2(son[u],t);
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==f[u]||edge[i].to==son[u]) continue;
		DFS2(edge[i].to,edge[i].to);
	}
}
#define lc (cur<<1)
#define rc (cur<<1|1)
struct Seg_Tree{
	int sum,l_ty,r_ty,tag;
}T[MAXN<<2];
il pushdown(int cur){
	if(!T[cur].tag) return ;
	T[lc].l_ty=T[rc].l_ty=T[cur].tag;
	T[lc].r_ty=T[rc].r_ty=T[cur].tag;
	T[lc].tag=T[rc].tag=T[cur].tag;
	T[lc].sum=T[rc].sum=1;
	T[cur].tag=0;
}
il pushup(int cur){
	T[cur].sum=T[lc].sum+T[rc].sum-(T[lc].r_ty==T[rc].l_ty);
	T[cur].l_ty=T[lc].l_ty;
	T[cur].r_ty=T[rc].r_ty;
}
il build_tree(int cur,int l,int r){
	if(l==r) T[cur].sum=1,T[cur].l_ty=T[cur].r_ty=val[rk[l]];
	else{
		build_tree(lc,l,mid),build_tree(rc,mid+1,r);
		pushup(cur);
	}
}
il updata(int cur,int l,int r,int L,int R,int k){
	if(l>=L&&r<=R) T[cur].tag=T[cur].l_ty=T[cur].r_ty=k,T[cur].sum=1;
	else{
		pushdown(cur);
		if(mid>=L) updata(lc,l,mid,L,R,k);
		if(R>mid) updata(rc,mid+1,r,L,R,k);
		pushup(cur);
	}
}
it query(int cur,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T[cur].sum;
	pushdown(cur);
	if(mid>=R) return query(lc,l,mid,L,R);
	if(L>mid) return query(rc,mid+1,r,L,R);
	return query(lc,l,mid,L,R)+query(rc,mid+1,r,L,R)-(T[lc].r_ty==T[rc].l_ty);
}
it query_col(int cur,int l,int r,int pos){
	if(l==r) return T[cur].l_ty;
	pushdown(cur);
	if(mid>=pos) return query_col(lc,l,mid,pos);
	else return query_col(rc,mid+1,r,pos);
}
il updata_path(int u,int v,int k){
	while(top[u]!=top[v]){
		if(d[top[u]]<d[top[v]]) swap(u,v);
		updata(1,1,n,id[top[u]],id[u],k);
		u=f[top[u]];
	}
	if(d[u]>d[v]) swap(u,v);
	updata(1,1,n,id[u],id[v],k);
}
it query_path(int u,int v){
	ri res=0;
	while(top[u]!=top[v]){
		if(d[top[u]]<d[top[v]]) swap(u,v);
		res+=query(1,1,n,id[top[u]],id[u])-(query_col(1,1,n,id[top[u]])==query_col(1,1,n,id[f[top[u]]]));
		u=f[top[u]];
	}
	if(d[u]>d[v]) swap(u,v);
	return res+query(1,1,n,id[u],id[v]);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i) read(val[i]);
	for(ri i=1;i<n;++i) read(u),read(v),add_edge(u,v);
	DFS1(1,0),DFS2(1,1),build_tree(1,1,n);
	for(ri i=1;i<=m;++i){
		scanf("%s",opt);read(u),read(v);
		if(opt[0]=='C') read(k),updata_path(u,v,k);
		else print(query_path(u,v)),puts("");
	}
	return 0;
}

总结

做题分类讨论的时候要仔细一点，不要讨论漏了。